/**
 * 1. 两数之和
 * https://leetcode-cn.com/problems/two-sum/
 */

// /**
//  * @description 桶排序
//  * @param {number[]} arr
//  * @return {number[]}
//  */
// const bucketSort = function (arr) {
//   const arrLength = arr.length;
//   const clone = Array.from(arr);
//   let max = clone[0];
//   let min = clone[0];
//   for (let i = 1; i < arrLength; i += 1) {
//     const cur = clone[i];
//     if (cur > max) {
//       max = cur;
//     } else if (cur < min) {
//       min = cur;
//     }
//   }
//   const bucketLength = max - min + 1;
//   const bucket = new Array(bucketLength);
//   for (let i = 0; i < arrLength; i += 1) {
//     const cur = clone[i];
//     const mapIndex = cur - min;
//     bucket[mapIndex] = (bucket[mapIndex] || 0) + 1;
//   }
//   let cloneIndex = 0;
//   for (let i = 0; i < bucketLength; i += 1) {
//     const count = bucket[i];
//     if (count > 0) {
//       const cur = i + min;
//       for (let j = 0; j < count; j += 1) {
//         clone[cloneIndex] = cur;
//         cloneIndex += 1;
//       }
//     }
//   }
//   return clone;
// };
//
// /**
//  * @description 二分法查找
//  * @param {number} target
//  * @param {number[]} arr
//  * @param {number} begin 起始位置（包含）
//  * @param {number} end 终点位置（包含）
//  * @return {number}
//  */
// const dichotomousFind = function (target, arr, begin, end) {
//   let _begin = begin;
//   let _end = end;
//   while (_begin < _end) {
//     const _middle = Math.floor((_begin + _end) / 2);
//     const cur = arr[_middle];
//     if (cur === target) return _middle;
//     if (cur < target) {
//       _begin = _middle + 1;
//     } else {
//       _end = _middle - 1;
//     }
//   }
//   return arr[_begin] === target ? _begin : -1;
// };
//
// /**
//  * @param {number[]} nums
//  * @param {number} target
//  * @return {number[]}
//  */
// const twoSum = function(nums, target) {
//   const numsLength = nums.length;
//   const numsEndIndex = numsLength - 1;
//   const sortedNums = Array.from(nums).sort(function (a, b) {
//     return a - b;
//   });
//   let n1;
//   let n2;
//   for (let i = 0; i < numsLength; i += 1) {
//     const cur = sortedNums[i];
//     const matchedNum = target - cur;
//     const matchedIndex = dichotomousFind(matchedNum, sortedNums, i + 1, numsEndIndex);
//     if (matchedIndex >= 0) {
//       n1 = cur;
//       n2 = matchedNum;
//       break;
//     }
//   }
//   const result = [0, 0];
//   let resultIndex = 0;
//   for (let i = 0; i < numsLength; i += 1) {
//     const cur = nums[i];
//     if (cur === n1 || cur === n2) {
//       result[resultIndex] = i;
//       resultIndex += 1;
//       if (resultIndex >= 2) break;
//     }
//   }
//   return result;
// };
//
// console.log(twoSum([2, 11, 7, 15], 9));

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = (nums, target) => {
  const map = new Map();
  const { length } = nums;
  for (let i = 0; i < length; i += 1) {
    const cur = nums[i];
    const matched = target - cur;
    const matchedIndex = map[matched];
    if (matchedIndex >= 0) {
      return [i, matchedIndex];
    }
    map[cur] = i;
  }
  return [0, 0];
};

console.log(twoSum([2, 11, 7, 15], 9));
